home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / vol_400 / 428_02 / libsrc / compress.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-03-13  |  6.0 KB  |  287 lines
  1. /*
  2. ** compress.c
  3. **
  4. ** Pictor, Version 1.51, Copyright (c) 1992-94 SoftCircuits
  5. ** Redistributed by permission.
  6. */
  7.  
  8. #include <stdio.h>
  9. #include <stdlib.h>
  10. #include <string.h>
  11.  
  12. #include "compress.h"
  13.  
  14. #define DEBUG  0     /* 1 = enable internal, fatal errors */
  15.  
  16. #define TABLE_SIZE   0xFF  /* number of different possible characters */
  17. #define MAX_BITS     50
  18.  
  19.  
  20. /* static variable declarations */
  21. static BYTE *buffer;
  22. static WORD index;
  23. static BYTE curr_bit;
  24. static NODE *leaf_table[TABLE_SIZE];
  25. static NODE *root_node;
  26.  
  27.  
  28. /*
  29. ** Writes a bit to the buffer.
  30. */
  31. static void write_bit(BYTE bit)
  32. {
  33.     if(curr_bit == 0) {
  34.         index++;
  35.         curr_bit = 1;
  36.     }
  37.  
  38.     if(bit == 0) {
  39.         buffer[index] &= ~curr_bit;
  40.     }
  41.     else {
  42.         buffer[index] |= curr_bit;
  43.     }
  44.     curr_bit <<= 1;
  45.  
  46. } /* write_bit */
  47.  
  48. /*
  49. ** Writes a node to the buffer.
  50. */
  51. static void write_node(NODE *node_ptr)
  52. {
  53.     static BYTE stack[MAX_BITS];
  54.     NODE *last_node;
  55.     WORD stack_ptr = 0;
  56.  
  57.     last_node = node_ptr;
  58.     node_ptr = node_ptr->parent;
  59.     for( ;last_node != root_node;node_ptr = node_ptr->parent) {
  60.  
  61. #if(DEBUG)
  62.  
  63.         /* caused by bad argument or corrupt code tree */
  64.         if(node_ptr == NULL) {
  65.             printf("Internal error : Module %s, Line %d\n",__FILE__,__LINE__);
  66.             exit(-1);
  67.         }
  68.         /* required bits exceed MAX_BITS (should never happen) */
  69.         if(stack_ptr >= MAX_BITS) {
  70.             printf("Internal error : Module %s, Line %d\n",__FILE__,__LINE__);
  71.             exit(-1);
  72.         }
  73.  
  74. #endif
  75.  
  76.         stack[stack_ptr++] = (BYTE)(node_ptr->child1 == last_node);
  77.         last_node = node_ptr;
  78.     }
  79.  
  80.     while(stack_ptr > 0) {
  81.         write_bit(stack[--stack_ptr]);
  82.     }
  83.  
  84. } /* write_node */
  85.  
  86. /*
  87. ** Compresses an array. Returns length of compressed array.
  88. */
  89. WORD compress(BYTE *in_array,WORD len,BYTE *out_array,NODE *root)
  90. {
  91.     WORD i;
  92.  
  93.     buffer = out_array;  /* set variables for write_bit() */
  94.     index = 0;
  95.     curr_bit = 1;
  96.  
  97.     root_node = root;
  98.  
  99.     for(i = 0;i < len;i++) {
  100.  
  101. #if(DEBUG)
  102.  
  103.         /* character found that was not included in compression code tree */
  104.         if(leaf_table[in_array[i]] == NULL) {
  105.             printf("Internal error : Module %s, Line %d\n",__FILE__,__LINE__);
  106.             exit(-1);
  107.         }
  108.  
  109. #endif
  110.  
  111.         write_node(leaf_table[in_array[i]]);
  112.     }
  113.     return(index + 1);
  114.  
  115. } /* compress */
  116.  
  117. /*
  118. ** Recursive portion of writetree().
  119. */
  120. static void _writetree(NODE *node_ptr)
  121. {
  122.     BYTE i;
  123.  
  124.     if(node_ptr->child0 == NULL) {   /* leaf node */
  125.         write_bit(0);
  126.         for(i = 1;i != 0;i <<= 1) {
  127.             write_bit((BYTE)(node_ptr->c & i));
  128.         }
  129.     }
  130.     else {
  131.         write_bit(1);
  132.         _writetree(node_ptr->child0);
  133.         _writetree(node_ptr->child1);
  134.     }
  135.  
  136. } /* _writetree */
  137.  
  138. /*
  139. ** Writes a bit-coded huffman code tree to a buffer.
  140. ** Returns the length of output buffer in bytes.
  141. */
  142. WORD writetree(NODE *root,BYTE *out_array)
  143. {
  144.     buffer = out_array;  /* set variables for write_bit() */
  145.     index = 0;
  146.     curr_bit = 1;
  147.  
  148.     _writetree(root);
  149.  
  150.     return(index + 1);
  151.  
  152. } /* writetree */
  153.  
  154. /*
  155. ** Combines two child nodes into a single branch node and
  156. ** returns a pointer to the branch.
  157. ** NULL indicates memory error.
  158. */
  159. static NODE *build_branch(NODE *child0,NODE *child1)
  160. {
  161.     NODE *node_ptr;
  162.  
  163.     node_ptr = malloc(sizeof(NODE));
  164.     if(node_ptr != NULL) {
  165.         node_ptr->parent = NULL;
  166.         node_ptr->freq = (child0->freq + child1->freq);
  167.         node_ptr->child0 = child0;
  168.         node_ptr->child1 = child1;
  169.         child0->parent = node_ptr;
  170.         child1->parent = node_ptr;
  171.     }
  172.     return(node_ptr);
  173.  
  174. } /* build_branch */
  175.  
  176. /*
  177. ** Constructs a code tree from node_list and returns the root node.
  178. ** NULL indicates memory.
  179. */
  180. static NODE *build_tree(NODE **node_list,WORD num_nodes)
  181. {
  182.     WORD i,min1,min2,index1 = 0,index2 = 0;
  183.     NODE *node_ptr = NULL;
  184.  
  185.     /* handle 1 or 0 nodes */
  186.     if(num_nodes <= 1) {
  187.         for(i = 0;i < TABLE_SIZE;i++) {
  188.             if(node_list[i] != NULL)
  189.                 return(node_list[i]);   /* 1 node */
  190.         }
  191.         /* if 0 nodes, return dummy node */
  192.         node_ptr = malloc(sizeof(NODE));
  193.         memset(node_ptr,'\0',sizeof(NODE));
  194.         return(node_ptr);
  195.     }
  196.  
  197.     /* construct code tree */
  198.     while(num_nodes > 1) {
  199.         min1 = min2 = 0xFFFF;
  200.         for(i = 0;i < TABLE_SIZE;i++) {
  201.             if(node_list[i] == NULL)
  202.                 continue;   /* already taken */
  203.             if(node_list[i]->freq < min1 || node_list[i]->freq < min2) {
  204.                 if(min1 < min2) {
  205.                     min2 = min1;
  206.                     index2 = index1;
  207.                 }
  208.                 min1 = node_list[i]->freq;
  209.                 index1 = i;
  210.             }
  211.         }
  212.         node_ptr = build_branch(node_list[index1],node_list[index2]);
  213.         if(node_ptr == NULL)
  214.             return(NULL);
  215.         node_list[index1] = node_ptr;
  216.         node_list[index2] = NULL;
  217.         num_nodes--;
  218.     }
  219.  
  220.     /* return root node */
  221.     return(node_ptr);
  222.  
  223. } /* build_tree */
  224.  
  225. /*
  226. ** Builds a code tree from the given file stream and returns a pointer
  227. ** to the root node. Returns NULL if no memory. NOTE: stream remains
  228. ** open when this function returns.
  229. */
  230. NODE *gettree(FILE *stream)
  231. {
  232.     WORD i,num_nodes;
  233.     WORD *freq_table;
  234.     NODE **node_list,*root = NULL;
  235.  
  236.     /* construct frequency table */
  237.     freq_table = malloc(TABLE_SIZE * sizeof(WORD));
  238.     if(freq_table == NULL) {
  239.         return(NULL);
  240.     }
  241.     memset(freq_table,'\0',TABLE_SIZE * sizeof(WORD));
  242.     for(i = (WORD)fgetc(stream);!feof(stream);i = (WORD)fgetc(stream)) {
  243.         freq_table[i]++;
  244.     }
  245.  
  246.     node_list = malloc(TABLE_SIZE * sizeof(NODE *));
  247.     if(node_list == NULL) {
  248.         free(freq_table);
  249.         return(NULL);
  250.     }
  251.  
  252.     /* build a leaf node for each character */
  253.     memset(leaf_table,'\0',sizeof(leaf_table));
  254.     for(num_nodes = 0,i = 0;i < TABLE_SIZE;i++) {
  255.         if(freq_table[i] != 0) {   /* if character is used */
  256.             leaf_table[i] = malloc(sizeof(NODE));
  257.             if(leaf_table[i] == NULL)
  258.                 break;;
  259.             leaf_table[i]->c = (BYTE)i;
  260.             leaf_table[i]->freq = freq_table[i];
  261.             leaf_table[i]->child0 = NULL;
  262.             leaf_table[i]->child1 = NULL;
  263.             leaf_table[i]->parent = NULL;
  264.             num_nodes++;
  265.         }
  266.         node_list[i] = leaf_table[i];
  267.     }
  268.  
  269.     free(freq_table);
  270.  
  271.     /* construct code tree if no error */
  272.     if(i == TABLE_SIZE)
  273.         root = build_tree(node_list,num_nodes);
  274.  
  275.     /* free memory if error */
  276.     if(root == NULL) {
  277.         for(i = 0;i < TABLE_SIZE;i++) {
  278.             if(leaf_table[i] != NULL) {
  279.                 free(leaf_table[i]);
  280.             }
  281.         }
  282.     }
  283.     free(node_list);
  284.     return(root);
  285.  
  286. } /* gettree */
  287.